#include<bits/stdc++.h>
//#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
//#pragma GCC optimize(2)
//#pragma GCC optimize(3)
//#pragma GCC optimize("Ofast,unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt,tune=native")
//#include <immintrin.h>
//#include <emmintrin.h>
#define ll long long
#define ls(x) (x<<1)
#define rs(x) (x<<1|1)
#define pii pair<int,int>
#define fi first
#define se second
#define Debug(...) fprintf(stderr, __VA_ARGS__)
#define For(i,a,b) for(int i=a,i##end=b;i<=i##end;i++)
#define Rof(i,a,b) for(int i=a,i##end=b;i>=i##end;i--)
#define rep(i,  b) for(int i=1,i##end=b;i<=i##end;i++)
using namespace std;
mt19937_64 rnd(time(0));
#define rand() abs((int)rnd())
const int N=1e6+5,base=999983,Mod=6661;
char buf[(1<<21)+5],*p1,*p2;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
inline void chmx(int &x,int y){(x<y)&&(x=y);}
inline void chmn(int &x,int y){(x>y)&&(x=y);}
inline int Mol(const int x){return (x>=Mod?x-Mod:x);}
inline ll read(){
	ll f=0,x=0;
	char ch=getchar();
	while(!isdigit(ch)){f|=(ch=='-');ch=getchar();}
	while(isdigit(ch)){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
	return f?-x:x;
}
void print(int n){
    if(n<0){
        putchar('-');
        n*=-1;
    }
    if(n>9) print(n/10);
    putchar(n%10+'0');
}
int n,m;ll k;
int C[Mod+5][Mod+5];
int qzh[Mod+5][Mod+5];
int Lucas(ll n,ll m){
	if(m==0) return 1;
	if(n<Mod&&m<Mod) return C[n][m];
	return (1ll*Lucas(n/Mod,m/Mod)*C[n%Mod][m%Mod])%Mod;
}
pair<ll,int> lz[N*3];
ll tr[N*3];
inline void pushup(int x){tr[x]=(tr[ls(x)]+tr[rs(x)]);}
void build(int x,int l,int r){
	if(l==r){
		tr[x]=Lucas(k,l);
		return ;
	}int mid=(l+r)>>1;
	build(ls(x),l,mid);build(rs(x),mid+1,r);
	pushup(x);
}
inline void down(int x,pair<ll,int> k,int l,int r){
	int p=(k.fi)%Mod,ss=(k.fi/Mod)%Mod;
	int L=(l-k.se)/Mod,R=(r-k.se)/Mod;
	if(!(L^R)){
		tr[x]=(qzh[p][(r-k.se)%Mod]-(!(l-k.se)%Mod?0:qzh[p][(l-k.se)%Mod-1])+Mod)*C[ss][L]; 
	}
	else{
		tr[x]=(qzh[p][Mod-1]-(!(l-k.se)%Mod?0:qzh[p][(l-k.se)%Mod-1])+Mod)*C[ss][L];
		tr[x]+=qzh[p][Mod-1]*(qzh[ss][R-1]-qzh[ss][L]+Mod);
		tr[x]+=(qzh[p][(r-k.se)%Mod])*C[ss][R];
	}
	if(l!=r)lz[x]=k;
}inline void pushdown(int x,int l,int r){
	if(lz[x].fi){
		int mid=(l+r)>>1;
		down(ls(x),lz[x],l,mid);
		down(rs(x),lz[x],mid+1,r);
		lz[x]={0,0};
	}
}
void updata(int x,int l,int r,int L,int R,pair<ll,int> k){
	if(L<=l&&r<=R) return down(x,k,l,r);
	int mid=(l+r)>>1;pushdown(x,l,r);
	if(L<=mid) updata(ls(x),l,mid,L,R,k);
	if(R>mid) updata(rs(x),mid+1,r,L,R,k);
	pushup(x);
}
ll qry(int x,int l,int r,int L,int R){
	if(L<=l&&r<=R) return tr[x];
	int mid=(l+r)>>1; ll res=0;pushdown(x,l,r);
	if(L<=mid) res=qry(ls(x),l,mid,L,R);
	if(R>mid) res+=qry(rs(x),mid+1,r,L,R);
	return res;
}
signed main(){
	freopen("izumi.in","r",stdin);
	freopen("izumi.out","w",stdout);
	// ios::sync_with_stdio(false);
	// cin.tie(0); cout.tie(0);
	C[0][0]=1;qzh[0][0]=1;
	For(j,0,Mod-1) qzh[0][j]=1;
	For(i,1,Mod-1){
		C[i][0]=1;qzh[i][0]=1;
		For(j,1,Mod-1){
			C[i][j]=Mol(C[i-1][j-1]+C[i-1][j]);
			qzh[i][j]=Mol(qzh[i][j-1]+C[i][j]);
		}
	}
	n=read(),m=read(),k=read();
	build(1,1,n);
	while(m--){
		int op=read(),l=read(),r=read();
		if(op==1){
			pair<ll,int>k;
			k.fi=read();k.se=l-1;
			updata(1,1,n,l,r,k);
		}else{
			print(qry(1,1,n,l,r)%Mod);puts("");
		}
	}
#ifdef LOCAL
    Debug("\nMy Time: %.3lfms\n", (double)clock() / CLOCKS_PER_SEC);
#endif
	return 0;
}

